package leetcode.editor.template.dp;

import java.util.Arrays;

public class DigitalDp {
    // 以233. 数字 1 的个数作为模板

    char[] s;
    int[][] memo;

    public int countDigitOne(int n) {
        s = Integer.toString(n).toCharArray();
        int m = s.length;
        // 根据题目给出的范围，一个数中 1 的数量最多只有 10 种情况
        memo = new int[m][10];
        // 初始化为 -1
        for (int i = 0; i < m; i++) Arrays.fill(memo[i], -1);
        return f(0, 0, true);
    }

    // 回从第 i 位开始，数字中 1 的个数
    public int f(int i, int oneCnt, boolean isLimit) {
        // 结束条件：到达此处的路径均为可行解，oneCnt 表示该可行解中 1 的数量
        if (i == s.length) return oneCnt;

        // 「没有限制」且「该状态结果已经计算出」，则直接返回
        if (!isLimit && memo[i][oneCnt] != -1) return memo[i][oneCnt];

        int up = isLimit ? s[i] - '0' : 9;

        int res = 0;
        for (int j = 0; j <= up; j++) {
            res += f(i + 1, oneCnt + (j == 1 ? 1 : 0), isLimit && j == up);
        }

        // 记录该状态的结果
        if (!isLimit) memo[i][oneCnt] = res;
        return res;
    }
}
